In digital data communication systems, a sequence of bits (i.e. a signal comprising binary digits) originates from a transmitter and is transmitted through a communications channel to a receiver. If the communication channel were perfect, the sequence of bits received at the receiver would be identical to the transmitted data bits. However, communications channels are not perfect and, because of the presence of noise and other spurious signals, the received data may very well not be the same as the transmitted data. Accordingly, systems have been designed to detect and correct errors occurring in sequences of received data. Such systems determine if some of the bits of the received data differ from the transmitted data, and thereafter correct the error or errors. The coding system disclosed herein permits the detection and correction of a single error occurring in a block (i.e. sequence) of bits.
A bit error occurring in a block of received digital data in data communication systems such as the videotex information system known, in Canada, as Telidon* (*an official mark of the Government of Canada, Ministry of Communications, for which notice has been given under Section 9(1) (n) (iii) of the Canadian Trade Marks Act) often results in noticeable and unacceptable picture distortion which, in turn, necessitates requesting, at the receiver, retransmission of that data block and waiting for some time interval before the retransmitted data block is received. Both picture distortion and retransmission delays are undesirable and may contribute to user/subscriber dissatisfaction with the data system. Consequently, it is desirable to be able to detect a bit error occurring in a block of received data bits and to correct the error within the receiver. Such error correction capability allows the correction of a bit error occurring in a block of data before the error results in picture distortion and eliminates having to wait for reception of the retransmitted data block.
Several single bit error correction methods are known, and many different apparatuses for encoding and decoding data blocks to permit the correction of a single bit error have been developed. For example, a group of data packets (e.g. bytes) may be horizontally and vertically parity encoded (i.e. non-algebraically encoded), denoted herein as the "Product Code", by using one parity bit in each byte and one code byte for each block of data bytes. To encode a block of data bytes using the Product Code one parity bit is appended to each group of 7 data bits to form parity encoded bytes. Then a byte (consisting of 8 bits), referred to as the Product Code byte, is determined and inserted in the data block. Each bit (e.g. the 3rd bit) of the Product Code byte is determined from the corresponding bits (e.g. the 3rd bits) in each of the data bytes and is set to either "0" or "1" according to the selected parity, i.e. the desired parity of those bits, taken as a group. The Product Code is a well known data encoding method. For a more detailed description of this coding method, reference should be made to information theory or coding textbooks, or both.
Another example of a single error correction method is known as the SAB code developed by G. E. Seguin, P. E. Allard and V. K. Bhargava and described in A Class of High Rate Codes for Byte-Oriented Information Systems, I.E.E.E. Transactions on Communications, Vol. COM-31, No. 3, March 1983.
Two disadavantages of the single bit error correction methods known heretofore, and equipment developed to implement those methods, are (i) the range of the number of data bits which can be encoded, and therefore corrected, by them, is narrow and (ii) some have a relatively high probability of making a decoding error or decoding failure when the communications channel transmitting the data includes white Gaussian noise and/or short noise bursts. (A "decoding error" may be defined as occurring when a bit correction is performed when the bit was correct or when a bit error is not corrected in the mistaken belief that no error occurred. A "decoding failure" may be defined as occurring when one or more errors are known to exist but where the erroneous bit(s) cannot be identified.) Consequently, it is desirable to develop a coding technique which can encode a wide range of numbers of data bits and which performs satisfactorily in the presence of either white Gaussian noise or short noise bursts.